package demo.practice.leetcode_msjd;

public class M0207 {

    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {

      /*  if(headA==null || headB==null)
            return null;

        Set<ListNode> nodes= new HashSet<>();
        ListNode cur= headA;
        while (cur!=null){
            nodes.add(cur);
            cur=cur.next;
        }
        cur= headB;
        while (cur!=null){
           if(nodes.contains(cur) )
               return cur;
           cur=cur.next;
        }

        return null;*/

        ListNode curA = headA;
        ListNode endA = null;
        int sizeA = 0;

        while (curA != null) {
            sizeA++;
            if (curA.next == null)
                endA = curA;
            curA = curA.next;
        }


        ListNode curB = headB;
        ListNode endB = null;
        int sizeB = 0;

        while (curB != null) {
            sizeB++;
            if (curB.next == null)
                endB = curB;
            curB = curB.next;
        }

        if (endA != endB)
            return null;

        if (sizeA > sizeB) {
            curA = headA;
            int step = sizeA - sizeB;//
            for (int i = 0; i < step; i++) {
                curA = curA.next;
            }

            curB=headB;
            while (curA!=curB){
                curA=curA.next;
                curB=curB.next;
            }

            return curA;
        }else{
            curB = headB;
            int step = -sizeA +sizeB;//
            for (int i = 0; i < step; i++) {
                curB = curB.next;
            }

            curA=headA;
            while (curA!=curB){
                curA=curA.next;
                curB=curB.next;
            }

            return curA;
        }

    }
}
